package gragh;

import java.io.Serializable;
import java.util.ArrayList;

import database.attset.SetAttribute;
import database.constraint.*;
import database.relation.Relation;
import database.relation.Table;

public class JoinGragh implements Serializable {

    /**
     * 
     */
    private static final long serialVersionUID = 1;
    private ArrayList<ArrayList<Integer>> lsWays;
    private ArrayList<Table> lsTable;
    private ArrayList<Relation> lsRelation;
    private ArrayList<Way> theWays;
    private final int MAX_STEP;
    
    private int[] stateNode;
    int[] stateEdge;
    
    public JoinGragh(ArrayList<Table> lsTb, ArrayList<Relation> lsRel) {
        MAX_STEP = lsTb.size() + 5;
        lsTable = lsTb;
        lsRelation = lsRel;
        stateNode = new int[lsTable.size()];
        theWays = new ArrayList<Way>();

          // khoi tao n dinh = n table
        lsWays = new ArrayList<ArrayList<Integer>>();
        for (int i = 0; i < lsTable.size(); i++) {
            lsWays.add(new ArrayList<Integer>());
        }
        
          // xet tung table mot
        for (int i = 0; i < lsTable.size(); i++) {
            Table tb = lsTable.get(i);
            Way way = null;
            
              // voi moi table, xet tung ref constraint cua no
            for (int j = 0; j < tb.getListConstraint().size(); j++) {
                  // chi lay ref constraint, ko lay pri-key constraint
                if (tb.getListConstraint().get(j).type == 1) {
                    ReferenceConstraint rc = (ReferenceConstraint) tb.getListConstraint().get(j);
                    
                    if (i != rc.refTableIndex) {
                        way = new Way();
                        way.table1 = i;
                        way.table2 = rc.refTableIndex;
                        for (Integer indexInTb : rc.ownerAttIndex) {
                            way.atts1.add(lsRel.get(way.table1).get(indexInTb));
                        }
                        for (Integer indexInTb : rc.refAttIndex) {
                            way.atts2.add(lsRel.get(way.table2).get(indexInTb));
                        }
                        theWays.add(way);
                        
                        int n = theWays.size() - 1;
                        lsWays.get(way.table1).add(n);
                        lsWays.get(way.table2).add(n);
                    }
                }
            }
        }
        
        stateEdge = new int[theWays.size()];
    }
    
    /**
     * Ham nay se quet toan do thi ket va tim ra cac cach ket co the gay du thua
     * @return
     */
    public ListRedundancy pathsAnalysis(ListRedundancy lsRedundancy) {
          // TEST
        number = 0;
        
          
        ListRedundancy lsR = lsRedundancy.clone();
        // TODO viet lai clone
        int step = 0;
        ArrayList<ArrayList<Integer>> currentChance = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> availableWays = null;
        int currentTb = 0;
        int maxIndexTb = 0;
        boolean fin = false;
        SetAttribute tables = new SetAttribute();
        SetAttribute paths = new SetAttribute();
        
          // xu ly du thua chi voi 1 dinh
        step = 1;
        for (int i = 0; i < lsTable.size(); i++) {
            tables.add(i);
            paths.add(i);
            for (Redundancy r : lsR) {
                r.updatePaths(tables, paths, lsRelation, theWays, step);
            }
            tables.clear();
            paths.clear();
        }
        
          // refesh step cua lsR
        for (Redundancy r : lsR) {
            if (r.step != 1) {
                r.step = MAX_STEP;
            }
        }
          // TODO xu ly cac truong hop thong thuong
        int startTb = 0;
        while (startTb < lsTable.size()) {
            tables.clear();
            paths.clear();
            fin = false;
            
              // INIT
              // 1. cap nhat currentTb
              // 2. cap nhat step
              // 3. cap nhat stateNode[]
              // 4. cap nhat maxIndexTb
              // 5. cap nhat tables
              // 6. cap nhat paths
              // 7. cap nhat currentChance
            currentTb = startTb;
            step = 1;
            stateNode[currentTb] = step;
            maxIndexTb = currentTb;
            tables.add(currentTb);
            paths.add(currentTb);
            availableWays = new ArrayList<Integer>();
            for (Integer indexWay : lsWays.get(currentTb)) {
                int linkedTb = getLinkedTable(currentTb, theWays.get(indexWay));
                  // nhung dinh them vao bat buoc phai lon hon dinh co index lon nhat
                if (linkedTb > maxIndexTb) {
                    if (stateNode[linkedTb] == 0) {
                        availableWays.add(indexWay);
                    }
                }
            }
            currentChance.add(availableWays);
            
            while (!fin) {
                int curChanceSize = currentChance.size();
                int curLastChanceSize = 0;
                  // su dung currentChance
                if (curChanceSize == 0) {
                    fin = true;
                } else {
                    curLastChanceSize = currentChance.get(curChanceSize-1).size();
                    if (curLastChanceSize == 0) {
                        if (!tables.isEmpty()) {
                              // 1. cap nhat currentTb
                              // 2. cap nhat step
                              // 3. cap nhat stateNode[]
                              // 4. cap nhat maxIndexTb
                              // 5. cap nhat tables
                              // 6. cap nhat paths
                              // 7. cap nhat currentChance
                              // 8. cap nhat step cua lsR
                            currentTb = tables.get(tables.size()-1);
                            step--;
                            stateNode[currentTb] = 0;
                            if (tables.size() > 1) {
                                maxIndexTb = tables.get(tables.size()-2);
                            } else {
                                maxIndexTb = -1;
                            }
                            tables.remove(tables.size()-1);
                            paths.remove(paths.size()-1);
                            currentChance.remove(curChanceSize-1);
                            if (step > 0) {
                                for (Redundancy r : lsR) {
                                    if (r.step > step) {
                                        r.step = MAX_STEP;
                                    }
                                }
                            }
                        } else {
                            fin = true;
                        }
                    } else {
                          // luc nay van con con duong de di
                        int indexWay_1 = currentChance.get(curChanceSize-1).get(curLastChanceSize-1);
                        currentChance.get(curChanceSize-1).remove(curLastChanceSize-1);
                        
                        Way way = theWays.get(indexWay_1);
                        int src = way.table1;
                        int des = way.table2;
                        
                          // 1. cap nhat currentTb
                          // 2. cap nhat step
                          // 3. cap nhat stateNode[]
                          // 4. cap nhat maxIndexTb
                          // 5. cap nhat tables
                          // 6. cap nhat paths
                          // 7. cap nhat currentChance
                        if (stateNode[src] != 0) {
                            currentTb = des;
                        } else {
                            currentTb = src;
                        }
                        step++;
                        stateNode[currentTb] = step;
                        maxIndexTb = currentTb;
                        tables.add(currentTb);
                        paths.add(indexWay_1);
                        availableWays = new ArrayList<Integer>();
                        for (int tb = 0; tb < stateNode.length; tb++) {
                            if (stateNode[tb] > 0) {
                                for (Integer indexWay : lsWays.get(tb)) {
                                    int linkedTb = getLinkedTable(tb, theWays.get(indexWay));
                                      // nhung dinh them vao bat buoc phai lon hon dinh co index lon nhat
                                    if (linkedTb > maxIndexTb) {
                                        if (stateNode[linkedTb] == 0) {
                                            availableWays.add(indexWay);
                                        }
                                    }
                                }
                            }
                        }
                        currentChance.add(availableWays);
                        
                          // sinh ra ket qua
                        for (Redundancy r : lsR) {
                            if (r.step > step) {
                                r.updatePaths(tables, paths, lsRelation, theWays, step);
                            }
                        }
                        printGNode(tables);
                    }
                }
            }
//            for (Integer indexWay : lsWays.get(start))
            startTb++;
        }
        
        System.out.println("Xong phan normal");
        

          // TODO xu ly truong hop 1 dinh co index cao noi lien voi 2 dinh co index thap hon
        ArrayList<SetAttribute> moreCase = new ArrayList<SetAttribute>();
        for (int indexT = 0; indexT < lsWays.size(); indexT++) {
            SetAttribute moreNodeNPath = new SetAttribute();
            moreNodeNPath.add(indexT);
            for (Integer gEdge : lsWays.get(indexT)) {
                int linkedT = getLinkedTable(indexT, theWays.get(gEdge));
                if (linkedT < indexT) {
                    moreNodeNPath.add(gEdge);
                }
            }
            
              // neu co hon 2 dinh co index nho hon
            if (moreNodeNPath.size() > 2) {
                moreCase.add(moreNodeNPath);
            }
        }
        
          // tao ra specialCase tu moreCase
        ArrayList<SetAttribute> specialCase = new ArrayList<SetAttribute>();
        for (SetAttribute moreNodeNPath : moreCase) {
            int tb = moreNodeNPath.get(0);
            moreNodeNPath.remove(0);
              // lay tat ca tap con thuc su
            ArrayList<SetAttribute> lsSubset = moreNodeNPath.listSubSetAttribute(moreNodeNPath);
            for (SetAttribute subset : lsSubset) {
                if (subset.size() > 1) {
                    SetAttribute sCase = new SetAttribute();
                    sCase.add(tb);
                    for (Integer inte : subset) {
                        sCase.add(inte);
                    }
                    specialCase.add(sCase);
                }
            }
              // lay them tap cha
            if (moreNodeNPath.size() > 1) {
                SetAttribute sCase = new SetAttribute();
                sCase.add(tb);
                for (Integer inte : moreNodeNPath) {
                    sCase.add(inte);
                }
                specialCase.add(sCase);
            }
        }
          // kiem tra va loai tru duong di da dinh vao cung 1 dinh
        int ikt = 0;
        while (ikt < specialCase.size()) {
            SetAttribute sCase = specialCase.get(ikt);
            SetAttribute ownedTb = new SetAttribute();
            ownedTb.add(sCase.get(0));
            
            boolean dup = false;
            int jkt = 1;
            while (!dup && jkt < sCase.size()) {
                int linkedTb = getLinkedTable(sCase.get(0), theWays.get(sCase.get(jkt)));
                if (ownedTb.contains(linkedTb)) {
                    dup = true;
                } else {
                    ownedTb.add(linkedTb);
                }
            }
            
            if (dup) {
                specialCase.remove(ikt);
            } else {
                ikt++;
            }
        }
        
        
          // xu ly tung sCase mot
        int maxStartTb = 0;
        while (!specialCase.isEmpty()) {
            tables.clear();
            paths.clear();
            currentChance.clear();
            
            SetAttribute sCase = specialCase.get(0);
            specialCase.remove(0);
            startTb = sCase.get(0);
            
              // INIT
              // 1. cap nhat step
              // 2. cap nhat stateNode[]
              // 3. cap nhat maxIndexTb
              // 4. cap nhat maxStartTb
              // 5. cap nhat tables
              // 6. cap nhat paths
              // 7. refesh step cua lsR
            step = 1;
            stateNode[currentTb] = step;
            maxIndexTb = -1;
            maxStartTb = startTb;
            tables.add(currentTb);
            paths.add(currentTb);
            for (Redundancy r : lsR) {
                if (r.step != 1) {
                    r.step = MAX_STEP;
                }
            }
          
              // 1. cap nhat currentTb
              // 2. cap nhat step (2, 3, 4 lam chung trong vong lap)
              // 3. cap nhat stateNode[]
              // 4. cap nhat maxIndexTb
              // 5. cap nhat tables
              // 6. cap nhat paths
              // 7. cap nhat currentChance
              // 8. cap nhat paths cho lsR
            for (int i = 1; i < sCase.size(); i++) {
                step++;
                Way w = theWays.get(sCase.get(i));
                int src = w.table1;
                int des = w.table2;
                if (startTb == src) {
                    currentTb = des;
                } else {
                    currentTb = src;
                }
                stateNode[currentTb] = step;
                maxIndexTb = currentTb;
                tables.add(currentTb);
                paths.add(sCase.get(i));
            }
            availableWays = new ArrayList<Integer>();
            for (int tb = 0; tb < startTb; tb++) {
                if (stateNode[tb] > 0) {
                    for (Integer indexWay : lsWays.get(tb)) {
                        int linkedTb = getLinkedTable(tb, theWays.get(indexWay));
                          // nhung dinh them vao bat buoc phai lon hon dinh co index lon nhat
                        if (linkedTb > maxIndexTb && linkedTb < startTb) {
                            if (stateNode[linkedTb] == 0) {
                                availableWays.add(indexWay);
                            }
                        }
                    }
                }
            }
            for (int tb = startTb; tb < stateNode.length; tb++) {
                if (stateNode[tb] > 0) {
                    for (Integer indexWay : lsWays.get(tb)) {
                        int linkedTb = getLinkedTable(tb, theWays.get(indexWay));
                          // nhung dinh them vao bat buoc phai lon hon dinh co index lon nhat
                        if (linkedTb > maxStartTb) {
                            if (stateNode[linkedTb] == 0) {
                                availableWays.add(indexWay);
                            }
                        }
                    }
                }
            }
            currentChance.add(availableWays);
            for (Redundancy r : lsR) {
                if (r.step > step) {
                    r.updatePaths(tables, paths, lsRelation, theWays, step);
                }
            }
            
            fin = false;
            while (!fin) {
                int curChanceSize = currentChance.size();
                int curLastChanceSize = 0;
                  // su dung currentChance
                if (curChanceSize == 0) {
                    fin = true;
                } else {
                    curLastChanceSize = currentChance.get(curChanceSize-1).size();
                    if (curLastChanceSize == 0) {
                        if (tables.size() > sCase.size()) {
                              // TODO thuc hien rollback
                              // 1. cap nhat currentTb
                              // 2. cap nhat step
                              // 3. cap nhat stateNode[]
                              // 4. cap nhat maxIndexTb
                              // 5. cap nhat maxStartTb
                              // 6. cap nhat tables
                              // 7. cap nhat paths
                              // 8. cap nhat currentChance
                              // 9. cap nhat step cua lsR
                            currentTb = tables.get(tables.size()-1);
                            step--;
                            stateNode[currentTb] = 0;
                            if (currentTb < startTb) {
                                maxIndexTb = -1;
                                for (int i = startTb-1; i >= 0; i--) {
                                    if (stateNode[i] > 0) {
                                        maxIndexTb = i;
                                        break;
                                    }
                                }
                            } else {
                                maxStartTb = -1;
                                for (int i = stateNode.length-1; i >= startTb; i--) {
                                    if (stateNode[i] > 0) {
                                        maxStartTb = i;
                                        break;
                                    }
                                }
                            }
                            tables.remove(tables.size()-1);
                            paths.remove(paths.size()-1);
                            currentChance.remove(curChanceSize-1);
                            if (step > 0) {
                                for (Redundancy r : lsR) {
                                    if (r.step > step && r.step != 1) {
                                        r.step = MAX_STEP;
                                    }
                                }
                            }
                        } else {
                            fin = true;
                        }
                    } else {
                          // luc nay van con con duong de di
                        int indexWay_1 = currentChance.get(curChanceSize-1).get(curLastChanceSize-1);
                        currentChance.get(curChanceSize-1).remove(curLastChanceSize-1);
                        
                        Way way = theWays.get(indexWay_1);
                        int src = way.table1;
                        int des = way.table2;
                        
                          // 1. cap nhat currentTb
                          // 2. cap nhat step
                          // 3. cap nhat stateNode[]
                          // 4. cap nhat maxIndexTb
                          // 5. cap nhat maxStartTb
                          // 6. cap nhat tables
                          // 7. cap nhat paths
                          // 8. cap nhat currentChance
                        if (stateNode[src] != 0) {
                            currentTb = des;
                        } else {
                            currentTb = src;
                        }
                        step++;
                        stateNode[currentTb] = step;
                        if (currentTb < startTb) {
                            maxIndexTb = currentTb;
                        } else {
                            maxStartTb = currentTb;
                        }
                        tables.add(currentTb);
                        paths.add(indexWay_1);
                          // TODO coi lai cach sinh dinh - copy tu tren kia xuong + chinh sua 1 chut
                        availableWays = new ArrayList<Integer>();
                        for (int tb = 0; tb < startTb; tb++) {
                            if (stateNode[tb] > 0) {
                                for (Integer indexWay : lsWays.get(tb)) {
                                    int linkedTb = getLinkedTable(tb, theWays.get(indexWay));
                                      // nhung dinh them vao bat buoc phai lon hon dinh co index lon nhat
                                    if (linkedTb > maxIndexTb && linkedTb < startTb) {
                                        if (stateNode[linkedTb] == 0) {
                                            availableWays.add(indexWay);
                                        }
                                    }
                                }
                            }
                        }
                        for (int tb = startTb; tb < stateNode.length; tb++) {
                            if (stateNode[tb] > 0) {
                                for (Integer indexWay : lsWays.get(tb)) {
                                    int linkedTb = getLinkedTable(tb, theWays.get(indexWay));
                                      // nhung dinh them vao bat buoc phai lon hon dinh co index lon nhat
                                    if (linkedTb > maxStartTb) {
                                        if (stateNode[linkedTb] == 0) {
                                            availableWays.add(indexWay);
                                        }
                                    }
                                }
                            }
                        }
                        currentChance.add(availableWays);
                        
                          // sinh ra ket qua
                        for (Redundancy r : lsR) {
                            if (r.step > step) {
                                r.updatePaths(tables, paths, lsRelation, theWays, step);
                            }
                        }
                        printGNode(paths);
                    }
                }
            }
        }
        
          // co the goi luc khac neu chay qua lau
        for (Redundancy r : lsR) {
            r.optimizePaths();
        }
        
        return lsR;
    }
    
      // TEST
    int number;
    public void printGNode(SetAttribute path) {
        number++;
        StringBuffer sb = new StringBuffer();
        for (Integer index : path) {
            sb.append(index + "-");
        }
        sb.deleteCharAt(sb.length()-1);
        System.out.println(sb.toString());
    }
    
    public int getLinkedTable(int curTb, Way way) {
        int result = -1;
        if (curTb == way.table1) {
            result = way.table2;
        } else if (curTb == way.table2) {
            result = way.table1;
        }
        return result;
    }
    
    public ArrayList<Way> getTheWays() {
        return theWays;
    }
    
    public void printMyself() {
        StringBuffer sb = new StringBuffer();
        
        for (int i = 0; i < lsWays.size(); i++) {
            sb.append(lsTable.get(i).getTableName() + " [link to] ");
            for (int j = 0; j < lsWays.get(i).size(); j++) {
                if (j != 0) {
                    sb.append(",");
                }
                Way way = theWays.get(lsWays.get(i).get(j));
                if (way.table1 == i) {
                    sb.append(lsTable.get(way.table2).getTableName());
                } else {
                    sb.append(lsTable.get(way.table1).getTableName());
                }
            }
            sb.append("\n");
        }
        
        System.out.println(sb.toString());
    }
    
    public void printMyself_vINT() {
        StringBuffer sb = new StringBuffer();
        
        for (int i = 0; i < lsWays.size(); i++) {
            sb.append((i+1) + " [link to] ");
            for (int j = 0; j < lsWays.get(i).size(); j++) {
                if (j != 0) {
                    sb.append(",");
                }
                Way way = theWays.get(lsWays.get(i).get(j));
                if (way.table1 == i) {
                    sb.append(way.table2+1);
                } else {
                    sb.append(way.table1+1);
                }
            }
            sb.append("\n");
        }
        
        System.out.println(sb.toString());
    }
    
    public void printWay_vINT() {
        StringBuffer sb = new StringBuffer();
        for (Way w : theWays) {
            sb.append(w.table1 + 1 + "-");
            sb.append(w.table2 + 1);
            sb.append("\n");
        }
        
        System.out.print(sb.toString());
    }
    
      // TEST
    public static void main(String[] args) {
        ArrayList<Table> lsTb = new ArrayList<Table>();
        ArrayList<Relation> lsRel = new ArrayList<Relation>();
        
        Table tb = new Table();    tb.index = 0;        lsTb.add(tb);
        
        tb = new Table();          tb.index = 1;        lsTb.add(tb);
        tb = new Table();          tb.index = 2;        lsTb.add(tb);
        tb = new Table();          tb.index = 3;        lsTb.add(tb);
        tb = new Table();          tb.index = 4;        lsTb.add(tb);
        tb = new Table();          tb.index = 5;        lsTb.add(tb);
        tb = new Table();          tb.index = 6;        lsTb.add(tb);
        
          // table 1
        ReferenceConstraint fc = new ReferenceConstraint();
        fc.type = 1;
        fc.ownerTableIndex = 0;
        fc.refTableIndex = 1;
        lsTb.get(0).getListConstraint().add(fc);
        
          // table 2
        fc = new ReferenceConstraint(); fc.type = 1; fc.ownerTableIndex = 1; fc.refTableIndex = 2;
        lsTb.get(1).getListConstraint().add(fc);
        
        fc = new ReferenceConstraint(); fc.type = 1; fc.ownerTableIndex = 1; fc.refTableIndex = 4;
        lsTb.get(1).getListConstraint().add(fc);
        
          // table 4
        fc = new ReferenceConstraint(); fc.type = 1; fc.ownerTableIndex = 3; fc.refTableIndex = 2;
        lsTb.get(3).getListConstraint().add(fc);
        
          // table 5
        fc = new ReferenceConstraint(); fc.type = 1; fc.ownerTableIndex = 4; fc.refTableIndex = 5;
        lsTb.get(4).getListConstraint().add(fc);
        
        fc = new ReferenceConstraint(); fc.type = 1; fc.ownerTableIndex = 4; fc.refTableIndex = 6;
        lsTb.get(4).getListConstraint().add(fc);
        
        JoinGragh jg = new JoinGragh(lsTb, lsRel);
        
        jg.printWay_vINT();
        System.out.println("---------------------------");
        jg.printMyself_vINT();
        System.out.println("---------------------------");
        ListRedundancy lsR = new ListRedundancy();
        jg.pathsAnalysis(lsR);
        System.out.println("Total: " + jg.number);
    }
    
    public class GNode {
        
    }

}
